#include <bits/stdc++.h>
using namespace std;


// 定义物品类
class Object
{
public:
	int id; // 物品编号
	int weight; // 物品重量
	int price; // 物品价格
	float d; // 单位重量价值
};

// 定义最大堆节点类
class MaxHeapQNode
{
public:
	MaxHeapQNode *parent; // 父节点指针
	int lchild; // 左子节点索引
	int upprofit; // 上一层的最优利润
	int profit; // 当前节点的总利润
	int weight; // 当前节点的总重量
	int lev; // 当前节点的层级
};

// 定义比较函数对象，用于优先队列中的元素比较
struct cmp
{
	bool operator()(MaxHeapQNode *&a, MaxHeapQNode *&b) const
	{
		return a->upprofit < b->upprofit; // 按照上一层的最优利润进行比较
	}
};

// 定义物品排序规则，按照单位重量价值从大到小排序
bool compare(const Object &a, const Object &b)
{
	return a.d >= b.d;
}

int n,c,cw,cp,bestp;
Object obj[100];
int bestx[100];


// 输入物品信息
void InPut()
{
	scanf("%d %d", &n, &c); // 输入物品数量和背包容量
	for(int i = 1; i <= n; ++i)
	{
		scanf("%d %d", &obj[i].price, &obj[i].weight); // 输入物品价格和重量
		obj[i].id = i; // 设置物品编号
		obj[i].d = 1.0 * obj[i].price / obj[i].weight; // 计算单位重量价值
	}
	
	sort(obj + 1, obj + n + 1, compare); // 根据单位重量价值对物品进行排序
}

// 计算上一层的最优利润
int Bound(int i)
{
	int tmp_cleft = c - cw; // 剩余容量
	int tmp_cp = cp; // 当前总利润
	while(tmp_cleft >= obj[i].weight && i <= n)
	{
		tmp_cleft -= obj[i].weight; // 减去当前物品的重量
		tmp_cp += obj[i].price; // 加上当前物品的价格
		i++;
	}
	if(i <= n)
	{
		tmp_cp += tmp_cleft * obj[i].d; // 计算剩余容量下的最大价值
	}
	return tmp_cp;
}

// 向优先队列中添加节点
void AddAliveNode(priority_queue<MaxHeapQNode *, vector<MaxHeapQNode *>, cmp> &q, MaxHeapQNode *E, int up, int wt, int curp, int i, int ch)
{
	MaxHeapQNode *p = new MaxHeapQNode; // 创建新节点
	p->parent = E; // 设置父节点
	p->lchild = ch; // 设置左子节点索引
	p->weight = wt; // 设置当前节点的总重量
	p->upprofit = up; // 设置上一层的最优利润
	p->profit = curp; // 设置当前节点的总利润
	p->lev = i + 1; // 设置当前节点的层级
	q.push(p); // 将新节点加入优先队列
}

// 求解最大背包问题
void MaxKnapsack()
{
	priority_queue<MaxHeapQNode *, vector<MaxHeapQNode *>, cmp > q; // 创建最大堆优先队列
	MaxHeapQNode *E = NULL; // 初始化根节点为空
	cw = cp = bestp = 0; // 初始化背包容量、当前总利润和最优总利润为0
	int i = 1; // 初始化物品索引为1
	int up = Bound(1); // 计算初始状态下的最优利润
	while(i != n + 1)
	{
		int wt = cw + obj[i].weight; // 计算当前节点的总重量
		if(wt <= c) // 如果当前节点可以放入背包
		{
			if(bestp < cp + obj[i].price) // 如果当前总利润大于最优总利润
				bestp = cp + obj[i].price; // 更新最优总利润
			AddAliveNode(q, E, up, cw + obj[i].weight, cp + obj[i].price, i, 1); // 将当前节点加入优先队列
		}
		up = Bound(i + 1); // 计算下一个状态的最优利润
		if(up >= bestp) // 如果下一个状态的最优利润大于等于当前最优利润
		{
			AddAliveNode(q, E, up, cw, cp, i, 0); // 将当前节点加入优先队列
		}
		E = q.top(); // 获取当前最优节点
		q.pop(); // 弹出当前最优节点
		cw = E->weight; // 更新背包容量
		cp = E->profit; // 更新当前总利润
		up = E->upprofit; // 更新上一层的最优利润
		i = E->lev; // 更新物品索引
	}
	for(int j = n; j > 0; --j) // 回溯最优解路径
	{
		bestx[obj[E->lev - 1].id] = E->lchild; // 记录装入的物品
		E = E->parent; // 更新当前节点为父节点
		if(E == NULL) break; // 如果已经到达根节点，跳出循环
	}
}

// 输出结果
void OutPut()
{
	printf("最优装入量为 %d\n", bestp); // 输出最优装入量
	printf("装入的物品为 \n"); // 输出装入的物品编号
	for(int i = 1; i <= n; ++i)
		if(bestx[i] == 1)
			printf("%d ", i); // 输出装入的物品编号
}

int main()
{
	InPut(); // 输入物品信息
	MaxKnapsack(); // 求解最大背包问题
	OutPut(); // 输出结果
	return 0;
}

